package com.ds.bintree.LeetCode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/9/19 14:27
 */
public class Num144_PreorderTraversal2 {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>(); //借助辅助栈
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur!=null){  //右边这个条件是防止弹出根节点后，右子树还有结点的情况
            while (cur!=null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            // 走到这里的时候左子树已经走到了最左下，该弹出最坐下结点，开始访问右子树了
            cur=stack.pop();
            cur = cur.right;
        }

        return list;
    }
}
